JZ15 翻转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {

    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode pre = head;
        ListNode cur = null;
        // 三指针
        while (pre != null) {
            ListNode temp = pre.next;
            pre.next = cur;
            cur = pre;
            pre = temp;
        }
        
        return cur;
    }
    
    // 方法二：最 low 的方法就是递归，这样会使用额外空间
    public ListNode ReverseList2(ListNode head) {
        //终止条件
        if (head == null || head.next == null) return head;
        // ===============递的阶段===============
        //保存当前节点的下一个结点
        ListNode next = head.next;
        //从当前节点的下一个结点开始递归调用
        ListNode reverse = ReverseList2(next); // 这里可以直接取得最后一个
        // ===============归的阶段===============
        // reverse 是反转之后的链表，因为函数 reverseList
        // 表示的是对链表的反转，所以反转完之后 next 肯定
        // 是链表reverse的尾结点，然后我们再把当前节点
        // head挂到next节点的后面就完成了链表的反转。
        next.next = head;

        // 这里head相当于变成了尾结点，尾结点都是为空的，否则会构成环
        head.next = null;
        return reverse;
    }

}

Go

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
*/
func ReverseList( pHead *ListNode ) *ListNode {
    if pHead == nil || pHead.Next == nil {
        return pHead
    }
    
    var cur *ListNode
    for pHead != nil {
        temp := pHead.Next
        pHead.Next = cur
        cur = pHead
        pHead = temp
    }
    
    return cur
}